Corelab Seminar
2011-2012
Chridtina Karousatou (NTUA)
All-Pairs Shortest Paths Computation in the BSP Model (Alexandre Tiskin)
Abstract (of the paper).
The model of bulk-synchronous parallel (BSP) computation
is an emerging paradigm of general-purpose parallel computing. We
propose a new p-processor BSP algorithm for the all-pairs shortest paths
problem in a weighted directed dense graph. In contrast with the general
algebraic path algorithm, which performs O(p^1/2) to O(p^2/3) global
synchronisation steps, our new algorithm only requires O(logp)
synchronisation steps.